package mianshi.huawei.medium;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/*
题目描述
Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，
但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？
样例输入
6
2 5 1 5 4 5
样例输出
3
提示
Example:
6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5
从第5格开始走最多有2步,4 5

所以这个结果是3。
接口说明
方法原型：
int GetResult(int num, int[] pInput, List  pResult);
输入参数：
int num：整数，表示数组元素的个数（保证有效）。
int[] pInput: 数组，存放输入的数字。
输出参数：
List pResult: 保证传入一个空的List，要求把结果放入第一个位置。
返回值：
正确返回1，错误返回0
输入描述:
输入多行，先输入数组的个数，再输入相应个数的整数
输出描述:
输出结果
示例1
输入
复制
6
2
5
1
5
4
5
输出
3

2 5 1 5 4 5
 */
//动态规划 NO
public class Redraiment {
    public static void main(String[] args) {
        System.out.println(GetResult(6,new int[]{2,5,1,5,4,5}));
    }

    public static int GetResult(int num, int[] pInput){
        int dp[] = new int[pInput.length];
        dp[0] = 1;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < pInput.length; i++) {
            //默认值为1
            dp[i] = 1;
            //从当前值往前找，找到比当前值小的结果+1，如果没有，则当前值为1
            for (int j = i; j >=0 ; j--) {
                if (pInput[i] > pInput[j]) {
                    dp[i] = dp[j] + 1;
                    break;
                }
            }
            //获取最大值
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static int GetResult(int num, int[] pInput, List pResult) {
        if (pInput == null || pInput.length != num) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < pInput.length; i++) {
            for (int j = 1; j < pInput.length; j++) {
                int number = pInput[i];
                int count = 1;
//186, 13, 322, 264, 328, 110, 120, 73, 20, 35, 240, 97, 150, 221, 284, 324, 46, 219, 239,
//                284, 128, 251, 298, 319, 304, 36, 144, 236, 163, 122
                for (int z = i + j; z < pInput.length; z++) {
                    if (pInput[z] > number) {
                        count++;
                        number = pInput[z];
                    }
                }
                max = Math.max(max, count);
            }

        }
        System.out.println(max);
        pResult = new ArrayList(1);
        pResult.add(max);
        return 1;
    }


}
